#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int ret = 0;
        int rowLen = grid.size();
        int colLen = grid[0].size();
        vector<int> rowVt(rowLen, 0);
        vector<int> colVt(colLen, 0);

        /* 获取水平方向最大值 */
        for (int row = 0; row < rowLen; row++) {
            int curMax = 0;
            for (int col = 0; col < colLen; col++) {
                curMax = max(curMax, grid[row][col]);
            }
            rowVt[row] = curMax;
        }
        /* 获取竖直方向最大值 */
        for (int col = 0; col < colLen; col++) {
            int curMax = 0;
            for (int row = 0; row < rowLen; row++) {
                curMax = max(curMax, grid[row][col]);
            }
            colVt[col] = curMax;
        }

        /* 遍历整个数组，获取每个位置可以增加的高度 */
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                ret = ret + min(rowVt[row], colVt[col]) - grid[row][col];
            }
        }
        return ret;
    }
};

int main()
{
    Solution s;
    vector<vector<int>> grid{{3,0,8,4},{2,4,5,7},{9,2,6,3},{0,3,1,0}};
    //vector<vector<int>> grid{{0,0,0},{0,0,0},{0,0,0}};
    cout << s.maxIncreaseKeepingSkyline(grid) << endl;
    return 0;
}